 public class ListNode {
      int val;
      ListNode next;
     ListNode(int val) {
          this.val = val;
      }
     ListNode(int val, ListNode next) {
          this.val = val; this.next = next;
      }

  }
 class Solution {
     public static void main(String[] args) {
         ListNode a1=new ListNode(4);
         ListNode a2=new ListNode(2);
         ListNode a3=new ListNode(1);
         ListNode a4=new ListNode(3);
      //   ListNode a5=new ListNode(0);
         a1.next=a2;
         a2.next=a3;
         a3.next=a4;
        // a4.next=a5;
         System.out.println(sortList(a1));
         System.out.println("==========");
     }
     public ListNode partition(ListNode pHead, int x) {
         // write code here
         //分割链表
          //创建一个哨兵位，两次循环
         if (pHead == null || pHead.next == null) {
             return pHead;
         }
         ListNode newhead=new ListNode(0);
         ListNode prev=newhead;
         ListNode cur=pHead.next;
         //将小于该结点的放入新链表后面
         while (cur!=null) {
             ListNode curNext=cur.next;
             if (cur.val<x) {
                 prev.next=cur;
                 prev=prev.next;
             }
             cur=curNext;
         }
         cur=pHead;
         while (cur!=null) {
             ListNode curNext=cur.next;
             if (cur.val>=x) {
                 prev.next=cur;
                 prev=prev.next;
             }
             cur=curNext;
         }
        prev.next=null;
         return newhead.next;

     }
     public static ListNode sortList(ListNode head) {
         if (head == null || head.next == null) {
             return head;
         }
         ListNode newhead=new ListNode(0);
         newhead.next=head;
         ListNode prev=head;
         ListNode cur=head.next;
         //定义prev的前一个结点的地址
         ListNode newprev=newhead;
         //定义一个指针记录最后一个结点的位置
         ListNode lastHead=prev;
         while (cur!=null) {
             newprev=newhead;
             prev=newprev.next;
             while (cur!=null&&prev!=cur) {
                ListNode curNext=cur.next;
                 if (lastHead.val<cur.val) {
                     lastHead.next=cur;
                     lastHead=cur;
                     cur=curNext;
                 }
                else if (prev.val>=cur.val) {
                    while (lastHead.next!=cur) {
                        lastHead=lastHead.next;
                    }
                    newprev.next=cur;
                    cur.next=prev;
                    lastHead.next=curNext;
                    prev=newhead.next;
                    newprev=newhead;
                    cur=curNext;
                }else {
                    //不大于的时候
                    newprev=prev;
                    prev=prev.next;
                }
            }
             if (cur!=null)
            cur=cur.next;
         }

         return newhead.next;
     }
     
 }